package top.retain;
import java.util.*;

/**
 * @author ivorfan
 * @date 2021/7/22 11:57
 */


public class Solution {

    public static void main(String[] args) {
        PriorityQueue<Integer> integers = new PriorityQueue<>(1, (o1, o2) -> o2 - o1);
        integers.add(1);
        integers.add(2);
        integers.add(3);
        integers.add(4);
        integers.add(5);


        Solution solution = new Solution();
        solution.LRU(new int[][]{{1,1,1},{1,2,2},{1,3,2},{2,1},{1,4,4},{2,2}}, 3);
    }

    static class ListNode{
        int key;
        int value;
        ListNode pre;
        ListNode next;
        public ListNode(){};
        public ListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private Map<Integer, ListNode> map = new HashMap<>();
    int size = 0;
    int cap;
    final ListNode head = new ListNode(-1,-1);
    final ListNode tail = new ListNode(-1,-1);
    public Solution() {
        head.next = tail;
        tail.pre = head;
    }

    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        this.cap = k;
        // write code here
        int m = operators.length;
        int n = operators[0].length;
        // 要打印的次数
        int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();
        int[] res = new int[len];
        for (int i=0, j = 0;i < m ; i++) {
            if (operators[i][0] == 1) {
                // put
                put(operators[i][1],operators[i][2]);
            }else {
                // get
                res[j++] = get(operators[i][1]);
            }
        }
        return res;
    }

    public int get(int key) {
        ListNode node = map.get(key);
        if (node == null) {
            return -1;
        }
        // 移动到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        ListNode node = map.get(key);
        // 不存在
        if (node == null) {
            node = new ListNode(key, value);
            // 超过大小
            if (size > cap) {
                // 移除末尾
                removeNode(tail.pre);
            }
            // 添加到首部
            addNode(node);
        }else {
            // 存在
            moveToHead(node);
        }
    }

    public void moveToHead(ListNode node) {
        removeNode(node);
        addNode(node);
    }
    // 删除节点
    public void removeNode(ListNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        map.remove(node.key);
        size--;
    }
    // 添加到队首
    public void addNode(ListNode node) {
        node.next = head.next;
        node.next.pre = node;
        head.next = node;
        node.pre = head;
        map.put(node.key, node);
        size++;
    }

}
